package features.advance.leetcode.interview.offer.medium;

import features.advance.jdk.dynamicproxy.cglib.CGlibProxy;
import features.advance.leetcode.Solution;
import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.tree.easy.Solution100;
import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;
import org.springframework.cglib.proxy.MethodProxy;

import java.lang.reflect.Method;
import java.math.BigDecimal;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 *
 *  剑指 Offer 26. 树的子结构
 *
 *  难度：中等
 *
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 B：
 *
 *    4
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 示例 1：
 *
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 * 示例 2：
 *
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 * 限制：
 *
 * 0 <= 节点个数 <= 10000
 *
 * @author LIN
 * @date 2021-05-06
 */
public class Offer26 extends Solution {

    public boolean isSubStructure(TreeNode A, TreeNode B){
       return (A != null && B != null) &&  recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right,B);
    }

    /**
     * 递归判断树A是否包含树B
     * @param A
     * @param B
     * @return
     */
    public boolean recur(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null || A.val != B.val){
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

    public static void main(String[] args) {

        Offer26 offer26 = new Offer26() {
        };
        String str = "[1,2,3,4,5,6,7,8,9,0]";
        ListNode node = TreeUtil.parseLinkedList(str);
        Set set = new LinkedHashSet<>();
        for (ListNode curr = node; curr !=null ;curr = curr.next) {
            int val = curr.val;
            set.add(val);
        }
        str = "[3,4,5,1,2,null,null,1,null]";
        TreeNode A = TreeUtil.parseArray(str);
        str = "[4,1]";
        TreeNode B = TreeUtil.parseArray(str);
        boolean subStructure = offer26.isSubStructure(A, B);
        System.out.println(subStructure);


        CGlibProxy proxy = new CGlibProxy(){
            @Override
            public Object intercept(Object o, Method method, Object[] objects, MethodProxy methodProxy) throws Throwable {
                System.out.println(method.getName());
                Object invoke = methodProxy.invokeSuper(o, objects);
                return invoke;
            }
        };
        Solution100 solution100 = (Solution100) proxy.createProxy(new Solution100());
        boolean sameTree = solution100.isSameTree(A, B);

        System.out.println(sameTree);
    }

    public void yangHuiTri(int param){
        BigDecimal triangle[][]=new BigDecimal[200][];
        // 创建二维数组
        // 遍历二维数组的第一层
        for (int i = 0; i < triangle.length; i++) {
            //控制行数,输出10行
            triangle[i] = new BigDecimal[i + 1];
            // 初始化第二层数组的大小
            // 遍历第二层数组
            for (int j = 0; j <= i; j++) {
                //控制列数
                // 将两侧的数组元素赋值为1
                if (i == 0 || j == 0 || j == i) {
                    triangle[i][j] = new BigDecimal("1");
                } else {
                    //其他数值通过公式计算
                    triangle[i][j] = triangle[i - 1][j].add(triangle[i - 1][j - 1]);
                }
                System.out.print(triangle[i][j] + "\t");
                // 输出数组元素
            }
            System.out.println();
            //换行
        }
    }
}
